package Greedy.leetcode;

/**
 * 1. 问题描述（leetcode 860题）
 *      在柠檬水摊上，每一杯柠檬水的售价为5美元。
 *      顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
 *      每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，
 *      也就是说净交易是每位顾客向你支付 5 美元。
 *      注意，一开始你手头没有任何零钱。
 *      如果你能给每位顾客正确找零，返回true，否则返回 false。

 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 柠檬水找零 {
    public static void main(String[] args) {

    }

    /**
     *
     * 算法实现(代码看上去比较难看)
     * 思路非常简单，没有用到任何算法，只是简单的组合而已
     *      首先我们判断bills[0]如果不等于5直接返回false，因为一开始我们没有零钱找
     *      其次我们设置三个变量count_5,count_10,count_20分别接受5，10，20三种零钱
     *      设置一个布尔变量 flag用于返回最终是否可以将所有顾客的零钱找开
     *      我们只用了一个for循环判断每一个bills[i]是否可以找开具体思路如下：
     *          如果当前bills[i] == 5,此时我们不需要找零钱，count_5 += 5
     *          如果当前bills[i] == 10,此时对于10元钱，我们只能通过5来找钱，
     *          所以之需要判断当前count_5是否为0(注意该变量一定是5的倍数，不会出现其他情况)
     *          如果不为0，则说明当前可以找零钱，然后count_10 += 10, count_5 -= 10
     *          如果当前bills[i] == 20,此时我们找零钱的方式只有三种：
     *              5 + 5 + 5
     *              5 + 10
     *              10 + 5
     *          所以此时我们判断：
     *              由上述分析可知此时count_5一定不能为0，否则不能找零钱
     *              我们分情况讨论
     *              if(count_5 >= 5 && count_10 >= 10) {
     *                     count_5 -= 5;
     *                     count_10 -= 10;
     *                     count_20 += 20;
     *                 } else if(count_5 >= 15){
     *                     count_5 -= 15;
     *                 } else {
     *                     flag = false;
     *                 }
     *              1. count_5 >= 5 && count_10 >= 10 OK
     *              2. count_5 >= 15 OK
     *              3. 其余not ok 解释一下为什么其余情况都是 not ok
     *              count_5 >= 5 count_10 >= 10的对偶为
     *              1. count_5 = 0 此时一定为false
     *              2. count_5 >= 5 count_10 = 10 此时
     *                  如果count_5 <= 15 false(结合else if的特性 此时count_5 <= 10)
     *              所以上述两条之一不满足一定不能找零钱
     * @param bills
     * @return
     */
    public static boolean lemonadeChange(int[] bills) {
        if(bills[0] != 5) {return false;} // 一开始我们没有钱可以找
        int count_5 = 0;
        int count_10 = 0;
        int count_20 = 0;
        boolean flag = true;
        for(int i = 0; i < bills.length; i++) {
            // 判断当前bills[i]能否找开零钱
            if(bills[i] == 5) {
                count_5+=5;
            }
            if(bills[i] == 10) {
                if(count_5 == 0) {
                    return false;
                }
                count_5 -= 5;
                count_10 += 10;
            }
            if(bills[i] == 20) { // 5 + 5 + 5 / 10 + 5 / 5 + 10 三种情况
                if(count_5 >= 5 && count_10 >= 10) {
                    count_5 -= 5;
                    count_10 -= 10;
                    count_20 += 20;
                } else if(count_5 >= 15){
                    count_5 -= 15;
                } else {
                    flag = false;
                }
            }
        }
        return flag;
    }

    /**
     * 贪心算法(对于找零钱一类的题，大部分和贪心算法有关)，我们考虑对于这个题而言，贪心的内容是什么?
     * 对于20这个数据而言，其实在这道题而言是一个无用的数据，因为我们只能找20，而不能通过20去找其他
     * 的零钱，对于5和10，实际上我们应该优先使用10去找零钱，5作为一个万精油如果10不够就去凑，所以此
     * 题贪心的内容为5的数量
     * 代码思路与上面类似，但是更加简洁，上述代码中有一些不必要的代码
     *
     * 首先设置两个变量来维护 int fives = 0; int tens = 0 分别维护5，10的数量
     * 循环遍历bills数组中的每一份账单，判断当前是否可以找零钱，优先使用10
     * @param bills
     * @return
     */
    public static boolean lemonadeChange2(int[] bills) {
        if(bills[0] != 5) {return false;}
        int fives = 0; int tens = 0;
        for(int money : bills) {
            if(money == 5) {fives++;}
            else if(money == 10) {
                if(fives > 0) {fives--; tens++;}
                else {return false;}
            } else {
                int t = 15; //需要找的钱的总额
                if(tens > 0) {t -= 10; tens--;}
                while(t > 0 && fives > 0) {
                    t -= 5;
                    fives--;
                }
                if(t > 0) {return false;}
            }
        }
        return true;
    }


}
